// 归并排序 就是分解分解排序合并排序合并的过程
// 1、分解2、排序3、合并
function mergeSort(arr) {
    const len = arr.length
    //说明此时数组已经是有序数组了
    if (len < 2) return arr
    let midder = len >> 1,//这实际上等同于将 len 除以2（但只取整数部分)
        left = arr.slice(0, midder),
        right = arr.slice(midder)
    return tool(mergeSort(left), mergeSort(right))
}
//排序有序数组 排序合并
function tool(left, right) {
    const result = []
    while (left.length && right.length) {
        if (left[0] >= right[0]) {
            result.push(right.shift())
        } else {
            result.push(left.shift())
        }
    }
    while (left.length) { result.push(left.shift()) }
    while (right.length) { result.push(right.shift()) }
    return result
}

let test = [1, 6, 3, 2, 7, 22, 6, 8, 9, 10, 16]
console.log(mergeSort(test));